package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/28/21 2:12 PM
 */
public class _16_按照左右半区的方式重新组合单链表 {

    public static Node join(Node root) {

        if (root == null || root.next == null || root.next.next == null || root.next.next.next == null) {

            return root;
        }

        Node slow = root;
        Node fast = root;

        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;
        }

        Node dummyNode = new Node();
        Node tailNode = dummyNode;

        Node node = root,post = slow;

        while (node != slow) {

            tailNode.next = node;
            node = node.next;
            tailNode = tailNode.next;
            tailNode.next = post;
            post = post.next;
            tailNode = tailNode.next;
        }

        if (post != null) {

            tailNode.next = post;
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {

        Node root = Nodes.generalNode(new int[]{1, 2, 3, 4, 5, 6, 7}, false);

        root = join(root);

        Nodes.printNode(root);

    }
}
